package Algorthim;

import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import junit.framework.Assert;

import org.apache.commons.lang3.StringUtils;

import com.rits.cloning.Cloner;

import phylogenetictree.Forest;
import phylogenetictree.PhylogeneticTree;

import searchTree.GlobalData;
import searchTree.searchTreeNode;

public abstract class Algorithim {
	//	Map<Integer,Map<Integer,String>> pathMap; // share this stuff through the constructors
	//	Map<Integer,Map<Integer,String>> pathMap2;
	//	ArrayList<searchTreeNode> soultions;
	protected GlobalData globaldata;
	Cloner cloner = new Cloner();
	public final static int FIRST = 1;
	public final static int BEST = 2;
	public final static int ALL = 3;
	public Boolean kernilise = false;

	public ArrayList<searchTreeNode> solve(String treeOne,String treeTwo,int option,int maxNumberOfCuts)
	{	
		PhylogeneticTree tree = null;
		PhylogeneticTree tree2 = null;
		try 
		{
			tree = new PhylogeneticTree(treeOne);
			tree2 = new PhylogeneticTree(treeTwo);
		} catch (IOException e)
		{
			e.printStackTrace();
		}

		return solve(tree,tree2,option,maxNumberOfCuts);
	}

	public ArrayList<searchTreeNode> solve(PhylogeneticTree treeOne,PhylogeneticTree treeTwo, int options, int maxNumberOfCuts)
	{
		if(kernilise)
		{
			// not currently implemented
			treeOne.kernelise(treeTwo);
		}

		searchTreeNode node = new searchTreeNode(treeOne);
		//		ArrayList<searchTreeNode> soultions = new Soultions(options, this.globaldata);
		this.globaldata = new GlobalData(buildPathMap(treeOne), buildPathMap(treeTwo), options, maxNumberOfCuts);
		ArrayList<searchTreeNode> soultions = new Soultions(options, this.globaldata);
		this.globaldata.setSoultions(soultions);
		phaseOne(node);

		if(options == Algorithim.BEST || options == Algorithim.FIRST)
		{
			int min = 10000;
			searchTreeNode bestAnswer = null;
			for(searchTreeNode n: soultions)
			{
				if(n.getNumberOfCuts() < min)					
				{
					min = n.getNumberOfCuts();
					bestAnswer = n;
				}
			}
			ArrayList<searchTreeNode> result = new ArrayList<searchTreeNode>();
			result.add(bestAnswer);

			//				JFrame dialogThree = new JFrame("soultion");
			//				dialogThree.setContentPane(Example.treeVeiwer(bestAnswer.getTree()));
			//				dialogThree.setVisible(true);

			return result;
		}
		else
		{
			return soultions;
		}
	}

	public void setGlobalData(GlobalData data)
	{
		this.globaldata = data;
	}

	protected Boolean doesEdesIntersect(int first,int secound,int third,int forth,PhylogeneticTree tree)
	{
		String pathOne = globaldata.getPathMap2().get(first).get(secound);
		String pathTwo = globaldata.getPathMap2().get(third).get(forth);
		return intersect(pathOne,pathTwo);
	}
	
	public void phaseOne(searchTreeNode node)
	{
		Map<Integer,Map<Integer,String>> pathMap = globaldata.getPathMap();
		Map<Integer,Map<Integer,String>> pathMap2 = globaldata.getPathMap2();
		Forest forest = node.getForest();
		PhylogeneticTree tree = forest.getTree();	
		tree.removepointlessVertexs();

		for(int repNum = 0; repNum < forest.getTreeRepsentitiveSize();repNum++)
		{
			Integer rep = forest.getTreeRepsentitive(repNum);
			if(tree.getNodeConnections(rep) == null || tree.getNodeConnections(rep).size() == 0)
			{
				forest.removeTreeRepsentitive(repNum);
				repNum--;
				continue;
			}

			Integer JunctionOne = tree.getNodeConnections(rep).get(0);
			Integer JunctionTwo;	
			Integer limitOne;
			Integer limitTwo;

			ArrayList<Integer> firstQuadrint = null;
			ArrayList<Integer> secoundQuadrint = null;
			ArrayList<Integer> thirdQuadrint = null;
			ArrayList<Integer> forthQuadrint = null;

			ArrayList<Integer[]> edges = new ArrayList<Integer[]>();

			edges = getInternalEdgesWithGuards(JunctionOne, -1, tree);
			if(edges.size() == 0)
			{
				forest.removeTreeRepsentitive(repNum);
				repNum--;
				continue;
			}

			// find minimal incompatible quartet
			for(Integer[] intEdge:edges)
			{
				JunctionOne = intEdge[0];			
				JunctionTwo = intEdge[3];

				limitOne = intEdge[1];
				limitTwo = intEdge[2];

				Boolean once = true;
				onceIncompatableFound:for(;once;)
				{
					once = false;
					Assert.assertTrue(!JunctionOne.equals(JunctionTwo));

					Integer[] result = getQuadrints(JunctionOne, limitOne,tree); 
					firstQuadrint = getleafs(result[0], JunctionOne, new ArrayList<Integer>(),tree);
					secoundQuadrint = getleafs(result[1], JunctionOne, new ArrayList<Integer>(),tree); 

					result = getQuadrints(JunctionTwo, limitTwo,tree); 
					thirdQuadrint = getleafs(result[0], JunctionTwo, new ArrayList<Integer>(),tree);
					forthQuadrint = getleafs(result[1], JunctionTwo, new ArrayList<Integer>(),tree);

					for(Integer first:firstQuadrint)
					{
						for(Integer secound:secoundQuadrint)
						{
							for(Integer third:thirdQuadrint)
							{
								for(Integer forth:forthQuadrint)
								{
									//								String testOne = pathMapTwo.get(translation.get(first.getId())).get(translation.get(secound.getId()));
									//								String testTwo = pathMapTwo.get(translation.get(third.getId())).get(translation.get(forth.getId()));
									//								System.out.println("quartlet ="  + "Limit One: " + limitOne + " Junction: " + JunctionOne +" "+ first.getId() + secound.getId() + "|" + third.getId() + forth.getId() +" Junction: " + JunctionTwo.getId() + " Limit two: " + limitTwo);

//									if(first.equals(forth) || first.equals(third) || secound.equals(forth) || secound.equals(third))
//									{
//										int x = 1+ 1;
//										x= x +1;
//									}
									
									
									if(doesEdesIntersect(first, secound, third, forth,tree))			 //	intersect(pathMap2.get(first).get(secound),pathMap2.get(third).get(forth)))
									{

										if(firstQuadrint.size() > 1)
										{
											for(Integer nn:firstQuadrint)
											{
												if(!nn.equals(first) && doesEdesIntersect(first,nn,third,forth,tree))
												{
													// extend internal quartet path 
													//												System.out.println("quartlet =" + first.getId() + nn.getId() + "|" + third.getId() + forth.getId());

													String pathOne = pathMap.get(nn).get(first);
													String pathTwo = pathMap.get(nn).get(JunctionOne);

													Integer intersection = null;
													for(Integer testIntersection:intersectRNode(pathOne, pathTwo))
													{
														if(tree.DoesNodeExcist(testIntersection) && !testIntersection.equals(JunctionTwo))
														{
															intersection = testIntersection;
															break;
														}
													}

													JunctionOne = intersection;
													String[] pathTwoSplit = pathMap.get(JunctionOne).get(JunctionTwo).split(",");
													int k =0;

													// handle when the next step in the path has been removed as well
													limitOne = Integer.valueOf(pathTwoSplit[k+1]);	
													while(!tree.DoesNodeExcist(limitOne))
													{
														k++;
														limitOne = Integer.valueOf(pathTwoSplit[k+1]);	
													}
													//												System.out.println("new JunctionOne " + JunctionOne.getId() + " limit is " + limitOne.getId()  + " for path" + pathTwo);
													once = true;
													continue onceIncompatableFound;
												}
											}
										}											

										if(secoundQuadrint.size() > 1)
										{
											for(Integer nn:secoundQuadrint)
											{
												if(!nn.equals(secound) && doesEdesIntersect(nn,secound,third,forth,tree))
												{
													// extend internal quartet path 
													//												System.out.println("quartlet =" + first.getId() + nn.getId() + "|" + third.getId() + forth.getId());

													String pathOne = pathMap.get(nn).get(secound);
													String pathTwo = pathMap.get(nn).get(JunctionOne);

													Integer intersection = null;
													for(Integer testIntersection:intersectRNode(pathOne, pathTwo))
													{
														if(tree.DoesNodeExcist(testIntersection) && !testIntersection.equals(JunctionTwo))
														{
															intersection = testIntersection;
															break;
														}
													}

													JunctionOne = intersection;
													String[] pathTwoSplit = pathMap.get(JunctionOne).get(JunctionTwo).split(",");
													int k =0;

													// handle when the next step in the path has been removed as well
													limitOne = Integer.valueOf(pathTwoSplit[k+1]);	
													while(!tree.DoesNodeExcist(limitOne))
													{
														k++;
														limitOne = Integer.valueOf(pathTwoSplit[k+1]);	
													}
													//												System.out.println("new JunctionOne " + JunctionOne.getId() + " limit is " + limitOne.getId()  + " for path" + pathTwo);
													once = true;
													continue onceIncompatableFound;
												}
											}
										}

										if(thirdQuadrint.size() > 1)
										{
											for(Integer nn:thirdQuadrint)
											{
												if(!nn.equals(third) && doesEdesIntersect(first,secound,third,nn,tree))
												{
													// extend internal quartet path 
													//												System.out.println("quartlet =" + first.getId() + nn.getId() + "|" + third.getId() + forth.getId());

													String pathOne = pathMap.get(nn).get(third);
													String pathTwo = pathMap.get(nn).get(JunctionTwo);

													Integer intersection = null;
													for(Integer testIntersection:intersectRNode(pathOne, pathTwo))
													{
														if(tree.DoesNodeExcist(testIntersection) && !testIntersection.equals(JunctionOne))
														{
															intersection = testIntersection;
															break;
														}
													}

													JunctionTwo = intersection;
													String[] pathTwoSplit = pathMap.get(JunctionTwo).get(JunctionOne).split(",");
													int k =0;

													// handle when the next step in the path has been removed as well
													limitTwo = Integer.valueOf(pathTwoSplit[k+1]);	
													while(!tree.DoesNodeExcist(limitTwo))
													{
														k++;
														limitTwo = Integer.valueOf(pathTwoSplit[k+1]);	
													}
													//												System.out.println("new JunctionOne " + JunctionOne.getId() + " limit is " + limitOne.getId()  + " for path" + pathTwo);
													once = true;
													continue onceIncompatableFound;
												}
											}
										}											

										if(forthQuadrint.size() > 1)
										{
											for(Integer nn:forthQuadrint)
											{
												if(!nn.equals(forth) && doesEdesIntersect(first,secound,nn,forth,tree))
												{
													// extend internal quartet path 
													//												System.out.println("quartlet =" + first.getId() + nn.getId() + "|" + third.getId() + forth.getId());

													String pathOne = pathMap.get(nn).get(forth);
													String pathTwo = pathMap.get(nn).get(JunctionTwo);

													Integer intersection = null;
													for(Integer testIntersection:intersectRNode(pathOne, pathTwo))
													{
														if(tree.DoesNodeExcist(testIntersection) && !testIntersection.equals(JunctionOne))
														{
															intersection = testIntersection;
															break;
														}
													}

													JunctionTwo = intersection;
													String[] pathTwoSplit = pathMap.get(JunctionTwo).get(JunctionOne).split(",");
													int k = 0;

													// handle when the next step in the path has been removed as well
													limitTwo = Integer.valueOf(pathTwoSplit[k+1]);	
													while(!tree.DoesNodeExcist(limitTwo))
													{
														k++;
														limitTwo = Integer.valueOf(pathTwoSplit[k+1]);	
													}
													//												System.out.println("new JunctionOne " + JunctionOne.getId() + " limit is " + limitOne.getId()  + " for path" + pathTwo);
													once = true;
													continue onceIncompatableFound;
												}
											}
										}

										// end of extending the internal paths

										if(node.getNumberOfCuts() < globaldata.getK())
										{
											handlePhaseOneReturn(node, first, JunctionOne, secound, JunctionTwo, third, forth);
											return;
										}		
										else
										{
											return;
										}

									}


								}
							}
						}
						break onceIncompatableFound;
					}
				}

			}


			// if subtree has no conflicting quartets ignore it
			forest.removeTreeRepsentitive(repNum);
			repNum--;
		}

		handlePhaseOneComplete(node);
	}

	protected abstract void handlePhaseOneReturn(searchTreeNode node, Integer firstleaf, Integer firstJunction, Integer secoundleaf, Integer secoundJunction, Integer thirdleaf, Integer forthleaf);

	protected abstract void handlePhaseOneComplete(searchTreeNode node);

	public void phaseTwo(searchTreeNode node)
	{
		PhylogeneticTree tree = node.getTree();
		Forest forest = node.getForest();
		Map<Integer,Map<Integer,String>> pathMap2 = globaldata.getPathMap2();

		tree.removepointlessVertexs();

		// create map two translation
		Map<Integer,Integer> translation = node.getTranslation();

		ArrayList<Integer> representitives = forest.getTreeRepsentitiveAll();
		ArrayList<ArrayList<Integer[]>> edgesInEachSubTree = new ArrayList<ArrayList<Integer[]>>();


		for(Integer repID:representitives)
		{
			edgesInEachSubTree.add(getEdges(repID, null, new ArrayList<Integer[]>(), new ArrayList<Integer>(),tree));
		}

		for(int subTreeNum = 0; subTreeNum < edgesInEachSubTree.size() - 1;subTreeNum++)
		{
			ArrayList<Integer[]> subTreeEdges = edgesInEachSubTree.get(subTreeNum);
			for(Integer[] edgeOne:subTreeEdges)
			{
				for(int otherSubTreeNum = subTreeNum + 1; otherSubTreeNum < edgesInEachSubTree.size(); otherSubTreeNum++)
				{
					ArrayList<Integer[]> otherSubTreeEdges = edgesInEachSubTree.get(otherSubTreeNum);
					for(Integer[] edgeTwo:otherSubTreeEdges)
					{
						boolean result = edgeOne[0].equals(edgeTwo[0]) || edgeOne[1].equals(edgeTwo[1]);
						boolean resultTwo = edgeOne[0].equals(edgeTwo[1]) || edgeOne[1].equals(edgeTwo[0]);

						//						System.out.println(edgeOne[0].getId() + ","+ edgeOne[1].getId() + " Compared Too " + edgeTwo[0].getId() + "," + edgeTwo[1].getId());

						//						try
						//						{

						if(edgeOne != edgeTwo && !result && !resultTwo) 
						{
//							String pathOne = pathMap2.get(translation.get(edgeOne[0])).get(translation.get(edgeOne[1]));
//							String pathTwo = pathMap2.get(translation.get(edgeTwo[0])).get(translation.get(edgeTwo[1]));
							if(doesEdesIntersect(translation.get(edgeOne[0]),translation.get(edgeOne[1]),translation.get(edgeTwo[0]),translation.get(edgeTwo[1]),tree))
							{
								if(node.getNumberOfCuts() >= globaldata.getK())
								{
									return;
								}

								handlePhaseTwoReturn(node, edgeOne, edgeTwo);
								return;
							}
						}

					}
				}
			}
		}

		globaldata.getSoultions().add(node);
	}

	protected abstract void handlePhaseTwoReturn(searchTreeNode node,Integer[] edgeOne,Integer[] edgeTwo);

	protected void createTranslation(searchTreeNode node)
	{
		Map<Integer,Integer> translation = new HashMap<Integer, Integer>();
		Map<Integer,Map<Integer,String>> pathMap2 = globaldata.getPathMap2();
		PhylogeneticTree tree = node.getTree();

		for(Integer n:tree.indexMap.keySet())
		{
			if(!tree.isLeaf(n))
			{
				tree.getNodeConnections(n).get(0);
				Integer one = getLeaf(n, tree.getNodeConnections(n).get(0),tree);
				Integer two = getLeaf(n,tree.getNodeConnections(n).get(1),tree);
				Integer three = getLeaf(n, tree.getNodeConnections(n).get(2),tree);

//				String pathOne = pathMap2.get(one).get(two);
//				String pathTwo = pathMap2.get(one).get(three);
//				String pathThree = pathMap2.get(two).get(three);

				translation.put(n,Integer.valueOf(intersectionOfThree(one, two, three,tree)));
			}
			else
			{
				translation.put(n, n);
			}
		}

		node.setTranslation(translation);
	}

	public ArrayList<Integer[]> getInternalEdgesWithGuards(Integer current,Integer parent,PhylogeneticTree tree)
	{
		return getInternalEdgesWithGuards(current, parent,new ArrayList<Integer[]>(),new ArrayList<Integer>(),new ArrayList<Integer>(), tree);
	}

	public ArrayList<Integer[]> getInternalEdgesWithGuards(Integer current,Integer parent,ArrayList<Integer[]> edges,ArrayList<Integer> nodesVisited,ArrayList<Integer> path, PhylogeneticTree tree)
	{
		Map<Integer,Map<Integer,String>> pathMap = globaldata.getPathMap();

		if(!tree.isLeaf(current) && path.size() >= 1)
		{
			for(Integer partner:nodesVisited)
			{
				String[] pathTwoSplit = pathMap.get(current).get(partner).split(",");
				int k =0;

				// handle when the next step in the path has been removed as well
				Integer limitOne = Integer.valueOf(pathTwoSplit[k+1]);	
				while(!tree.DoesNodeExcist(limitOne))
				{
					k++;
					limitOne = Integer.valueOf(pathTwoSplit[k+1]);	
				}

				Integer nodeTwo = Integer.valueOf(pathTwoSplit[pathTwoSplit.length - 1]);

				k = pathTwoSplit.length - 2;

				Integer limitTwo = Integer.valueOf(pathTwoSplit[k]);	
				while(!tree.DoesNodeExcist(limitTwo))
				{
					k--;
					limitTwo = Integer.valueOf(pathTwoSplit[k]);	
				}


				Integer[] edge = new Integer[]{current,limitOne,limitTwo,nodeTwo};
				Integer[] edgeRev = new Integer[]{nodeTwo,limitTwo,limitOne,current};
				if(!contains(edges,edge) && !contains(edges,edgeRev))
				{
					edges.add(edge);
				}
			}
		}

		if(!tree.isLeaf(current))
		{
			nodesVisited.add(current);
		}

		for(Integer c:tree.getNodeConnections(current))
		{
			if(!c.equals(parent))
			{
				ArrayList<Integer> newPath = cloner.shallowClone(path);
				newPath.add(current);
				getInternalEdgesWithGuards(c, current, edges, nodesVisited, newPath, tree);

			}
		}
		return edges;
	}

	public Map<Integer, Map<Integer, String>> buildPathMap(PhylogeneticTree tree)
	{
		Map<Integer,Map<Integer,String>> allPaths = new HashMap<Integer, Map<Integer,String>>();
		for(int i = 0; i < tree.getAdjacencyList().length;i++)
		{
			if(tree.DoesNodeExcist(i))
			{
				mapToBuild = new HashMap<Integer, String>();
				getpaths(i, -1,"",tree);
				allPaths.put(i, mapToBuild);
			}
		}
		return allPaths;		
	}

	Map<Integer,String> mapToBuild;

	// look at alternatives to using recursion ? might fix the lack of heap space error
	private Map<Integer,String> getpaths(Integer base,Integer Parent,String path,PhylogeneticTree tree) // ,Map<String,String> mapToBuild)
	{
		if(path.length() == 0)
		{
			path = String.valueOf(base);
		}
		else
		{
			path += "," + base;
		}

		mapToBuild.put(base,path);
		for(Integer n:tree.getNodeConnections(base))
		{
			if(Parent == -1 || !n.equals(Parent))
			{
				getpaths(n,base,path,tree); // ,mapToBuild);
			}
		}
		return mapToBuild;
	}

	public static Integer[] getQuadrints(Integer Junction,Integer limit,PhylogeneticTree tree)
	{
		Integer arg = null;
		Integer arg2 = null;
		for(Integer n:tree.getNodeConnections(Junction))
		{
			if(!n.equals(limit))
			{
				if(arg == null)
				{
					arg = n;
				}
				else if(arg2 == null)
				{
					arg2 = n;
				}
			}
		}
		return new Integer[]{arg,arg2};
	}

	public Integer getLeaf(Integer current,Integer parent,PhylogeneticTree tree)
	{
		if(tree.isLeaf(current))
		{
			return current;
		}

		for(Integer child:tree.getNodeConnections(current))
		{
			if(!child.equals(parent))
			{
				if(tree.isLeaf(child))
				{
					return child;
				}
				else // need to change to test for null and ignore if it gets found
				{
					Integer result = getLeaf(child, current, tree);
					if(result != null)
					{
						return result;
					}
				}
			}
		}
		return null;
	}

	public ArrayList<Integer> getleafs(Integer node,Integer parent,ArrayList<Integer> leafs,PhylogeneticTree tree)
	{
		if(tree.isLeaf(node))
		{
			leafs.add(node);
		}
		else
		{
			for(Integer n:tree.getNodeConnections(node))
			{
				if(parent == null || !n.equals(parent))
				{
					getleafs(n,node,leafs,tree);
				}
			}
		}
		return leafs;
	}

	private boolean contains(ArrayList<Integer[]> array, Integer[] item) 
	{
		for(Integer[] member:array)
		{
			if(member[0].equals(item[0]) && member[3].equals(item[3]))
			{
				return true;
			}
		}
		return false;
	}


	public static boolean intersect(String one,String two)
	{
		String[] result = one.split(",");
		String[] result2 = two.split(",");
		for(String first:result)
		{
			for(String secound:result2)
			{
				if(first.equals(secound))
				{
					return true;
				}
			}
		}				
		return false;
	}

	
	protected String intersectionOfThree(int one, int two, int three, PhylogeneticTree tree)
	{
		String pathOne = globaldata.getPathMap2().get(one).get(two);
		String pathTwo = globaldata.getPathMap2().get(one).get(three);
		String pathThree = globaldata.getPathMap2().get(two).get(three);
		return intersect(pathOne, pathTwo, pathThree);
	}
	
	public static String intersect(String one,String two,String three)
	{
		String[] stringOne = one.split(",");
		String[] stringTwo = two.split(",");
		String[] stringThree = three.split(",");

		//			int indexOne = 0,indexTwo = 0,indexThree = 0;

		for(String first:stringOne)
		{
			for(String secound:stringTwo)
			{
				if(StringUtils.equals(first, secound))
				{
					for(String third:stringThree)
					{
						if(StringUtils.equals(first, third))
						{
							return first;
						}
					}
				}
			}
		}

		return null;
	}

	public static ArrayList<Integer> intersectRNode(String one,String two)
	{
		String[] stringOne = one.split(",");
		String[] stringTwo = two.split(",");
		ArrayList<Integer> result= new ArrayList<Integer>();

		//int indexOne = 0,indexTwo = 0,indexThree = 0;

		for(String first:stringOne)
		{
			if(stringOne[0].equals(first) || stringOne[stringOne.length - 1].equals(first))
			{
				continue;
			}
			for(String secound:stringTwo)
			{
				if(StringUtils.equals(first, secound))
				{
					result.add(Integer.valueOf(first));
				}
			}
		}

		return result;
	}

	public synchronized ArrayList<Integer[]> getEdges(Integer current,Integer parent,ArrayList<Integer[]> edges,ArrayList<Integer> nodesVistited,PhylogeneticTree tree) 
	{
		for(Integer n:tree.getNodeConnections(current))
		{
			if(!edges.contains(new Integer[]{n,current}) && !edges.contains(new Integer[]{current,n}) && n != current) 
			{
				edges.add(new Integer[]{n,current});
			}
		}

		nodesVistited.add(current); // internal edges being added twice

		for(Integer c:tree.getNodeConnections(current))
		{
			if(!c.equals(parent))
			{
				getEdges(c,current, edges,nodesVistited,tree);
			}
		}		
		return edges;
	}
}
